# coding=utf-8
# Date: 2021/9/8 9:58
from typing import List
from queue import PriorityQueue


# 执行用时：1008 ms, 在所有 Python3 提交中击败了6.67%的用户
# 内存消耗：36.4 MB, 在所有 Python3 提交中击败了44.00%的用户
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        q = []
        n = len(profits)
        for i in range(n):
            q.append([capital[i], profits[i]])
        q.sort()

        heap = PriorityQueue()
        i = 0
        for _ in range(k):
            while i < n and q[i][0] <= w:
                heap.put(-q[i][1])                                         
                i += 1
            if heap.qsize() == 0:
                break
            t = -heap.get()
            w += t
        return w


if __name__ == "__main__":
    print(Solution().findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1]))
